package com.platform.modules.alg.alglib.poj3368;

public class Poj3368 {
    public String output = "";

    private final int maxn = 100010;
    int a[] = new int[maxn]; // 数据
    int lb[] = new int[maxn]; // 存储 log 值
    int F[][] = new int[maxn][20]; // F(i,j) 表示区间 [i，i+2^j-1] 的最值，区间长度为 2^j

    void Initlog() {//求解所有log值,保存到数组lb[]
        lb[0] = -1;
        for (int i = 1; i < maxn; i++)
            lb[i] = (i & (i - 1)) > 0 ? lb[i - 1] : lb[i - 1] + 1;
    }

    void ST_create(int n) {//每个测试用例n不同，因此做参数
        for (int j = 1; j <= lb[n]; j++)
            for (int i = 1; i <= n - (1 << j) + 1; i++)//n-2^j+1
                F[i][j] = Math.max(F[i][j - 1], F[i + (1 << (j - 1))][j - 1]);
    }

    int RMQ(int l, int r) {//求区间[l..r]的最值差
        if (l > r) return 0;
        int k = lb[r - l + 1];
        return Math.max(F[l][k], F[r - (1 << k) + 1][k]);
    }

    public String cal(String input) {

        int n, q, l, r;
        Initlog();

        String[] line = input.split("\n");
        String[] words = line[0].split(" ");
        n = Integer.parseInt(words[0]);
        q = Integer.parseInt(words[1]);

        String[] nums = line[1].split(" ");

        for (int i = 1; i <= n; i++) { // 下标从1开始
            a[i] = Integer.parseInt(nums[i - 1]);
            if (i == 1) {
                F[i][0] = 1;
                continue;
            }
            if (a[i] == a[i - 1])
                F[i][0] = F[i - 1][0] + 1;
            else
                F[i][0] = 1;
        }
        ST_create(n);
        for (int j = 1; j <= q; j++) {
            String[] query = line[j + 1].split(" ");
            l = Integer.parseInt(query[0]);
            r = Integer.parseInt(query[1]);

            int t = l;
            while (t <= r && a[t] == a[t - 1])
                t++;
            output += Math.max(t - l, RMQ(t, r)) + "\n";
        }
        return output;
    }
}
